package _01_sort;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: mornd
 * @dateTime: 2023/6/23 - 12:48
 * 基数排序（依靠桶来完成）
 * 根据数字的位数从低位到高位依次进行排序
 * 最低有效数组LSD (least significant digit)
 */
public class RadixSort {

    @Test
    public void test() {
//        String[] arr = {"173", "163", "259", "149", "146"};
        String[] arr = {"2547381924", "1872495648", "5385967452",
                        "9182746352", "6537586958", "6538271649"};
        radixSort(arr, 10);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 173 163 259 149 146
     * 173 163 146 259 149  比较个位数
     * 146 149 259 163 173  比较十位数
     * 146 149 163 173 259  比较百位数
     * 依此类推...
     *
     * @param arr
     * @param length 数组中元素的长度
     */
    public void radixSort(String[] arr, int length) {
        // 长度为10，只能处理0~9的字符
        List<List<String>> buckets = new ArrayList<>(10); // 0~9
        // 初始桶
        for (int i = 0; i < 10; i++) {
            buckets.add(new ArrayList<>());
        }

        for (int j = length - 1; j >= 0; j--) {
            for (String str : arr) {
                // 位数的值就对应桶的下标位置
                int num = str.charAt(j) - '0'; // 0对应的int值为 48
                buckets.get(num).add(str);
            }

            // 将桶中元素取出，替换掉原数组
            int index = 0;
            for (List<String> bucket : buckets) {
                for (String str : bucket) {
                    arr[index++] = str;
                }
                // 取出元素后再清空桶，用于下次比较
                bucket.clear();
            }
        }
    }
}
